//初始化dp数组
int **initDP(int m, int n) {
    //动态开辟dp数组
    int **dp = (int**)malloc(sizeof(int *) * m);
    int i, j;
    for(i = 0; i < m; ++i) {
        dp[i] = (int *)malloc(sizeof(int) * n);
    }

    //从0，0到i,0只有一种走法，所以dp[i][0]都是1，同理dp[0][j]也是1
    for(i = 0; i < m; ++i)
        dp[i][0] = 1;
    for(j = 0; j < n; ++j)
        dp[0][j] = 1;
    return dp;
}

int uniquePaths(int m, int n){
    //dp数组，dp[i][j]代表从dp[0][0]到dp[i][j]有几种走法
    int **dp = initDP(m, n);

    int i, j;
    //到达dp[i][j]只能从dp[i-1][j]和dp[i][j-1]出发
    //dp[i][j] = dp[i-1][j] + dp[i][j-1]
    for(i = 1; i < m; ++i) {
        for(j = 1; j < n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    int result = dp[m-1][n-1];
    free(dp);
    return result;
}